package com.example.suanfademo;

/**
 * 滴滴面试   查找链表的倒数第m个元素
 */
public class FindMthFromEnd {
    class ListNode {
        int val;
        ListNode next;
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public  Integer findMthFromEnd(ListNode head, int m) {
        if (head == null || m <= 0) return null;

        ListNode fast = head;
        ListNode slow = head;

        for (int i = 0; i < m; i++) {
            if (fast == null) return null;
            fast = fast.next;
        }

        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }

        return slow.val;
    }

    public ListNode createLinkedList(int[] values) {
        if (values == null || values.length == 0) return null;

        ListNode head = new ListNode(values[0]);
        ListNode current = head;

        for (int i = 1; i < values.length; i++) {
            current.next = new ListNode(values[i]);
            current = current.next;
        }

        return head;
    }


    public static void main(String[] args) {
        FindMthFromEnd findMthFromEnd =new FindMthFromEnd();
        // 创建测试链表: 1 → 2 → 3 → 4 → 5
        ListNode head = findMthFromEnd.createLinkedList(new int[]{1, 2, 3, 4, 5});

        System.out.println("原始链表:");
        System.out.println();

        // 测试各种情况
        System.out.println("测试结果:");
        System.out.println("倒数第1个: " +findMthFromEnd.findMthFromEnd(head, 1));  // 5
        System.out.println("倒数第2个: " + findMthFromEnd.findMthFromEnd(head, 2));  // 4
        System.out.println("倒数第3个: " + findMthFromEnd.findMthFromEnd(head, 3));  // 3
        System.out.println("倒数第5个: " + findMthFromEnd.findMthFromEnd(head, 5));  // 1
        System.out.println("倒数第6个: " + findMthFromEnd.findMthFromEnd(head, 6));  // null
        System.out.println("倒数第0个: " + findMthFromEnd.findMthFromEnd(head, 0));  // null
    }
}
